МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 2 З ДИСЦИПЛІНИ “АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” Затверджено на засiданнi кафедри “Захист інформації”, протокол № від 2008 р. Львів – 2008 Дослідження швидкодії виконання мультиплікативних операцій з довгими числами: Методичні вказівки до лабораторної роботи №2 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” /Укл.: А.Е.Лагун, В.М.Іванюк - Львів: НУЛП 2008. - 00 с. Укладачі: А.Е.Лагун, к.т.н., доцент В.М.Іванюк, асистент Відповідальний за випуск: І.Я. Тишик, старший викладач. Рецензент: В.В.Максимович, д.т.н., професор. Мета роботи - вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел. 1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ 1.1. Множення довгих чисел з використанням стовпчика. При виконанні операції множення довгих чисел можна скористатися моделюванням стовпчика, виконуючи на кожному кроці перенесення в наступний розряд.
рис.1. Блок-схема алгоритму, що реалізує арифметичну операцію множення довгого числа на коротке. Блок-схема одиного з варіантів алгоритму множення довгого числа на коротке, де коротке число є беззнаковим цілим (unsigned int), наведена на рис.1. Використовується додаткова змінна t для визначення кількості розрядів результату і формування перенесення в наступний розряд. Довге число записане в масиві a, а коротке – в змінній b. В першу чергу значення результату обнулюється. Далі перевіряється, чи короткий множник дорівнює 0. Якщо так, то в результаті буде число нуль. Інакше відбувається формування розрядів результату множення, які дорівнюють остачі від ділення на основу системи числення добутку розряду довгого множника на короткий множник плюс розряд перенесення. Значення перенесення в наступний розряд результату є цілою частиною від ділення добутку ai*b+t на основу системи числення. На останньому кроці формуються значення кількості розрядів результату, старші розряди результату за рахунок цілочисельного ділення та остачі цілочисельного ділення значення перенесення t на основу системи числення. Алгоритм множення довгого числа на довге (рис.2) подібний до описаного вище алгоритму множення за винятком того, що під час формування розрядів результату перемножуються відповідні розряди довгих чисел ai та bi. Також відбувається додавання до кожного розряду результату множення значення проміжного множення на окремий розряд tti. 1.2. Алгоритм ділення довгих чисел. Ділення двох довгих чисел полягає в знаходженні цілої частини частки і остачі. Вважаємо, що дільник – це число, яке ділить, ділене – число, на яке ділять, частка – результат ділення. Можливі три випадки. якщо дільник дорівнює діленому, то ціла частина результату дорівнює 1, а остача 0; якщо дільник менший за ділене, то ціла частина частки дорівнює нулю, а остача – дільнику; якщо дільник більший за ділене, то необхідна підпрограма ділення двох довгих чисел.
рис.2. Блок-схема алгоритму множення довгих чисел способом стовпчика. 1000143123567    |  73859998 -73859998 | 13541 (Ціла частина частки) 261543143 - 221579994   399631495 - 369299990     303315056 295439992    78750647 - 73859998    4890649 (Залишок) Далі починаються проблеми. Наприклад, поділимо стовпчиком два довгі числа 1000143123567 і 73859998. На кожному етапі підбирається цифра (1, 3, 5 і т.д.), така, що добуток цієї цифри на дільник дає число менше, але н...